package com.hspedu.newData.dmsxl.链表.快慢指针;

import com.hspedu.newData.dmsxl.ds.ListNode;

import java.util.HashSet;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-04-22 
 * @Version: 1.0
 */

public class LC142环形链表Ⅱ {

    // 哈希表实现
    public ListNode detectCycle(ListNode head) {

        HashSet<ListNode> set = new HashSet<>();

        while(head!= null){
            if (set.contains(head)){
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }

    // 快慢指针实现
    public ListNode detectCycle1(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast){
                ListNode cur = head;
                while (cur != slow){
                    cur = cur.next;
                    slow = slow.next;
                }
                return cur;
            }
        }

        return null;
    }

}
